/*
 * @lc app=leetcode.cn id=63 lang=java
 *
 * [63] 不同路径 II
 */

// @lc code=start
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 二维动态规划
        // f(i, j) = f(i-1, j) + f(i, j-1)
        // 注意：障碍物的处理
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        // int[][] dp = new int[m][n];

        // // 初始化
        // for(int i = 0; i < m; i++) {
        //     if(obstacleGrid[i][0] == 1) {
        //         break;
        //     }
        //     dp[i][0] = 1;
        // }
        // for(int j = 0; j < n; j++) {
        //     if(obstacleGrid[0][j] == 1) {
        //         break;
        //     }
        //     dp[0][j] = 1;
        // }

        // // 状态转移
        // for(int i = 1; i < m; i++) {
        //     for(int j = 1; j < n; j++) {
        //         // 障碍物
        //         if(obstacleGrid[i][j] == 1) {
        //             dp[i][j] = 0;
        //         } else {
        //             dp[i][j] = dp[i-1][j] + dp[i][j-1];
        //         }
        //     }
        // }
        // return dp[m-1][n-1];

        // 空间优化
        int[] dp = new int[n];
        dp[0] = (obstacleGrid[0][0] == 0) ? 1 : 0;

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(obstacleGrid[i][j] == 1) {
                    dp[j] = 0;
                    
                } 
                // dp[j] = 左边和上一次迭代的值
                
                else if(j - 1 >= 0 && obstacleGrid[i][j-1] == 0) {
                    dp[j] += dp[j-1];
                }
            }
        }
        return dp[n-1];
    }
}
// @lc code=end

